package com.peng.leetcode.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * TreeMain
 * 1. 完全二叉树:
 * 叶子节点全部在最底下2层,
 * 最后一层的叶子节点全部靠左排列,
 * 并且除了最后一层其他的层的节点个数全部达到了最大
 * <p>
 * 2. 二叉树的数组存储
 * 将根节点放在数组下标为 i = 1 的位置, 左子节点放到下标为 i * 2 的位置 右子节点放到 i * 2 + 1 的位置
 *
 * @author: lupeng6
 * @create: 2020/12/25 14:34
 */
public class TreeMain {


    public static void main(String[] args) {
        Integer[] array = {5, 3, 7, 2, 4, 6, 8};
        TreeNode root = array2tree(array);
        System.out.println("----------------前序------------------");
        preOrder(root).forEach(System.out::println);
        System.out.println("----------------层序------------------");
        layerOrder(root).forEach(System.out::println);
        System.out.println("----------------中序------------------");
        inOrder(root).forEach(System.out::println);
        System.out.println("----------------后序------------------");
        postOrder(root).forEach(System.out::println);
        System.out.println("----------------查找------------------");
        System.out.println(searchNode(root, 6));
        System.out.println("----------------插入------------------");
        insert(root, 1);
//        layerOrder(root).forEach(System.out::println);
        inOrder(root).forEach(System.out::println);

//        System.out.println("----------------删除------------------");
//        delete(root, 5);
//        inOrder(root).forEach(System.out::println);

        System.out.println("----------------二叉树的高度------------------");
        System.out.println(treeHeight(root));
    }

    /**
     * 数组转换成二叉树
     *
     * @author lupeng6
     * @date 2020/12/25 15:12
     */
    public static TreeNode array2tree(Integer[] array) {
        int index = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(array[index++]);
        queue.offer(root);

        int length = array.length;
        while (index < length) {
            TreeNode node = queue.poll();

            Integer leftValue = array[index];
            if (leftValue != null) {
                node.left = new TreeNode(leftValue);
                queue.offer(node.left);
            }
            index++;

            if (index < length) {
                Integer rightValue = array[index];
                if (rightValue != null) {
                    node.right = new TreeNode(rightValue);
                    queue.offer(node.right);
                }
            }
            index++;
        }

        return root;
    }



    /**
     * 二叉树的前序遍历
     *
     * @author lupeng6
     * @date 2020/12/25 14:47
     */
    public static List<Integer> preOrder(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> integers = new ArrayList<>();
        integers.add(root.val);
        List<Integer> leftArr = preOrder(root.left);
        List<Integer> rightArr = preOrder(root.right);
        if (leftArr != null) {
            integers.addAll(leftArr);
        }
        if (rightArr != null) {
            integers.addAll(rightArr);
        }
        return integers;
    }


    /**
     * 二叉树的中序遍历
     *
     * @author lupeng6
     * @date 2020/12/25 14:47
     */
    public static List<Integer> inOrder(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> integers = new ArrayList<>();

        List<Integer> leftArr = inOrder(root.left);
        if (leftArr != null) {
            integers.addAll(leftArr);
        }

        integers.add(root.val);

        List<Integer> rightArr = inOrder(root.right);
        if (rightArr != null) {
            integers.addAll(rightArr);
        }
        return integers;
    }


    /**
     * 二叉树的后序遍历
     *
     * @author lupeng6
     * @date 2020/12/25 14:47
     */
    public static List<Integer> postOrder(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<Integer> integers = new ArrayList<>();
        List<Integer> leftArr = postOrder(root.left);
        if (leftArr != null) {
            integers.addAll(leftArr);
        }

        List<Integer> rightArr = postOrder(root.right);
        if (rightArr != null) {
            integers.addAll(rightArr);
        }

        integers.add(root.val);
        return integers;
    }

    /**
     * 二叉树的层级遍历
     *
     * @author lupeng6
     * @date 2020/12/25 15:13
     */
    public static List<Integer> layerOrder(TreeNode root) {
        List<Integer> result = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        return result;
    }

    /**
     * 二叉搜索树的查找
     *
     * @author lupeng6
     * @date 2020/12/25 15:37
     */
    public static int searchNode(TreeNode root, int target) {
        if (root == null) {
            return -1;
        }
        TreeNode dummy = root;
        while (dummy != null) {
            if (dummy.val == target) {
                return dummy.val;
            }
            if (target > dummy.val) {
                dummy = dummy.right;
            }

            if (target < dummy.val) {
                dummy = dummy.left;
            }
        }
        return -1;
    }

    /**
     * 二叉搜索的插入
     *
     * @author lupeng6
     * @date 2020/12/25 15:38
     */
    public static void insert(TreeNode root, int target) {
        if (root == null) {
            root = new TreeNode(target);
        }
        TreeNode dummy = root;
        while (dummy != null) {
            if (target > dummy.val) {
                if (dummy.right == null) {
                    dummy.right = new TreeNode(target);
                    return;
                }
                dummy = dummy.right;
            } else {
                if (dummy.left == null) {
                    dummy.left = new TreeNode(target);
                    return;
                }
                dummy = dummy.left;
            }
        }
    }

    /**
     * 二叉搜索树的删除
     * 递归的方式
     * https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/
     *
     * @author lupeng6
     * @date 2020/12/25 15:44
     */
    public static TreeNode delete(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        if (target > root.val) {
            root.right = delete(root.right, target);
        }
        if (target < root.val) {
            root.left = delete(root.left, target);
        }
        if (target == root.val) {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.right != null) {
                root.val = rightTreeSuccessor(root);
                root.right = delete(root.right, root.val);
            } else {
                root.val = leftTreeSuccessor(root);
                root.left = delete(root.left, root.val);
            }
        }
        return root;
    }

    /**
     * 右子树的继承者
     *
     * @author lupeng6
     * @date 2020/12/25 17:41
     */
    public static int rightTreeSuccessor(TreeNode root) {
        root = root.right;
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }

    public static int leftTreeSuccessor(TreeNode root) {
        root = root.left;
        while (root.right != null) {
            root = root.right;
        }
        return root.val;
    }

    /**
     * 二叉树的高度
     *
     * @author lupeng6
     * @date 2020/12/25 19:58
     */
    public static int treeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftTreeHeight = treeHeight(root.left) + 1;
        int rightTreeHeight = treeHeight(root.right) + 1;
        return Math.max(leftTreeHeight, rightTreeHeight);
    }

}
